class Solution(object):
    def letterCombinations(self, digits):
        """
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

        :type digits: str
        :rtype: List[str]
        """
        dict = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
        }

        def helper(digits):
            if len(digits) == 0:
                return []
            if len(digits) == 1:
                return list(dict[digits[0]])
            first = list(dict[digits[0]])
            remains = helper(digits[1:])
            return [ f + r for f in first for r in remains]

        return helper(digits)